//
//  File.swift
//  iOSAlgorithm
//
//  Created by Mr.Wei on 2021/5/6.
//

import Foundation

//判断字符串中的"()"是否能够正确配对，能正确配对的字符串视为有效字符串。
//字符串中只有"("和")"
//空串视为有效
func isValidString(string:String?) -> Bool {
    //string 如果是 nil 则 返回 false
    guard let string = string else { return  true }
    //string 长度为 0 则 返回 false
    if string.count == 0 {
        return true
    }
    //长度为奇数则一定是无效字符串
    if string.count % 2 == 1 {
        return false
    }
//    var a = Stack<Character>();
//    for i in string {
//        if i == "(" {
//            a.push(i)
//        }
//        if i == ")" {
//            if a.pop() == nil {
//                return false
//            }
//        }
//    }
//    if a.count > 0 {
//        return false
//    }
    //优化 1
    //使用栈存储数据的逻辑，但没必要真的存，记个数就可以了。
    var leftNum = 0
    for i in string {
        if i == "(" {
            leftNum += 1
        }
        if i == ")" {
            if leftNum <= 0 {
                return false
            }
            leftNum -= 1
        }
    }
    if leftNum != 0 {
        return false
    }
    return true
}


//判断字符串中的"()"是否能够正确配对，能正确配对的字符串视为有效字符串。
//字符串中除只有"("和")"之外，还有"[","]"和"{","}"
//空串视为有效
func isValidString2(string:String?) -> Bool {
    //string 如果是 nil 则 返回 false
    guard let string = string else { return  true }
    //string 长度为 0 则 返回 false
    if string.count == 0 {
        return true
    }
    //长度为奇数则一定是无效字符串
    if string.count % 2 == 1 {
        return false
    }
    //入栈的括号不止一种  只计数就不行了  必须真实入栈了
    var a = Stack<Character>()
    for i in string {
        if i == "(" || i == "[" || i == "{"{
            a.push(i)
        }else if i == ")" {
            guard let pop = a.pop() else { return false }
            if pop != "(" {
                return false
            }
        }else if i == "]" {
            guard let pop = a.pop() else { return false }
            if pop != "[" {
                return false
            }
        }else if i == "}" {
            guard let pop = a.pop() else { return false }
            if pop != "{" {
                return false
            }
        }
    }
    if a.count > 0 {
        return false
    }
    return true
}
